import { Circle, Line, Point, Rect, Segment, segmentsIntersect } from "../src/shared/utils/MathUtil"

/** 范围 */
export interface Bounds {
    /** 左下角x坐标 */
    x: number,
    /** 左下角y坐标 */
    y: number,
    /** 宽度 */
    w: number,
    /** 高度 */
    h: number,
    id?: number,
}
/** 四叉树 */
export default class QuadTree {

    /** 范围 */
    bounds: Bounds
    /** 四叉树最大深度 */
    private maxDeep: number
    /** 单个树最大容量 */
    private maxNum: number
    /** 当前深度 */
    private deep: number
    //叶子节点
    leafs: Bounds[]
    //树
    nodes: QuadTree[]

    constructor(bounds: Bounds, deep: number, maxDeep?: number, maxNum?: number) {
        this.bounds = bounds
        this.deep = deep
        this.maxDeep = maxDeep || 3
        this.maxNum = maxNum || 4
        this.nodes = []
        this.leafs = []
    }

    /** 分割 */
    private split() {

        const x = this.bounds.x
        const y = this.bounds.y
        const w = this.bounds.w / 2
        const h = this.bounds.h / 2
        const nextDeep = this.deep + 1

        this.nodes[0] = new QuadTree(
            {
                x: x + w,
                y: y + h,
                w: w,
                h: h,
            },
            nextDeep,
        )

        this.nodes[1] = new QuadTree(
            {
                x: x,
                y: y + h,
                w: w,
                h: h,
            },
            nextDeep,
        )

        this.nodes[2] = new QuadTree(
            {
                x: x,
                y: y,
                w: w,
                h: h,
            },
            nextDeep,
        )

        this.nodes[3] = new QuadTree(
            {
                x: x + w,
                y: y,
                w: w,
                h: h,
            },
            nextDeep,
        )

    }

    private getIndex(rect: Rect): number[] {
        const mindX = this.bounds.w / 2 + this.bounds.x
        const mindY = this.bounds.h / 2 + this.bounds.y

        const maxX = rect.x + rect.w
        const maxY = rect.y + rect.h
        const minX = rect.x
        const minY = rect.y

        const inTop = maxY > mindY
        const inBottom = minY < mindY
        const inLeft = minX < mindX
        const inRight = maxX > mindX

        const indexs: number[] = []

        if (inRight && inTop) {
            indexs.push(0)
        }
        if (inLeft && inTop) {
            indexs.push(1)
        }
        if (inLeft && inBottom) {
            indexs.push(2)
        }
        if (inRight && inBottom) {
            indexs.push(3)
        }
        return indexs
    }

    /** 矩形碰撞检测 */
    retrieve(rect: Rect): Bounds[] {

        const leafs: Bounds[] = []
        if (this.leafs.length == 0 && this.nodes.length == 0) {
            return leafs
        }
        if (this.leafs.length) {
            leafs.push(...this.leafs)
        } else {
            const indexs = this.getIndex(rect)
            for (let i = 0; i < indexs.length; i++) {
                leafs.push(...this.nodes[indexs[i]].retrieve(rect))
            }
        }

        return leafs.filter((v, i) => leafs.indexOf(v) === i)
    }

    /** 圆形碰撞 */
    retrieveByCircule(cir: Circle): Bounds[] {

        const leafs: any = []
        if (this.leafs.length == 0 && this.nodes.length == 0) {
            return leafs
        }
        if (this.leafs.length) {
            leafs.push(...this.leafs)
        } else {
            const indexs = this.getIndexByCircle(cir)
            for (let i = 0; i < indexs.length; i++) {
                leafs.push(...this.nodes[indexs[i]].retrieveByCircule(cir))
            }
        }

        return leafs.filter((v: any, i: number) => leafs.indexOf(v) === i)
    }

    /** 点碰撞 */
    retrieveByPoint(p: Point): Bounds[] {

        const leafs: any = []
        if (this.leafs.length == 0 && this.nodes.length == 0) {
            return leafs
        }
        if (this.leafs.length) {
            leafs.push(...this.leafs)
        } else {
            const indexs = this.getIndexByPoint(p)
            for (let i = 0; i < indexs.length; i++) {
                leafs.push(...this.nodes[indexs[i]].retrieveByPoint(p))
            }
        }

        return leafs.filter((v: any, i: number) => leafs.indexOf(v) === i)
    }

    /** 线段碰撞 */
    retrieveByLine(line: Line): Bounds[] {

        const leafs: any = []
        if (this.leafs.length == 0 && this.nodes.length == 0) {
            return leafs
        }
        if (this.leafs.length) {
            leafs.push(...this.leafs)
        } else {
            const indexs = this.getIndexByLine(line)
            for (let i = 0; i < indexs.length; i++) {
                leafs.push(...this.nodes[indexs[i]].retrieveByLine(line))
            }
        }

        return leafs.filter((v: any, i: number) => leafs.indexOf(v) === i)
    }

    private getIndexByCircle(cir: Circle): any {

        const mindX = this.bounds.w / 2 + this.bounds.x
        const mindY = this.bounds.h / 2 + this.bounds.y

        const rectX = this.bounds.x
        const rectY = this.bounds.y
        const rectWidth = this.bounds.w
        const rectHeight = this.bounds.h

        const circleX = cir.px
        const circleY = cir.py
        const circleR = cir.r

        const fun = (rectTop: number, rectBottom: number, rectLeft: number, rectRight: number) => {
            // 检查圆心是否在矩形之外
            if (
                circleX > rectRight + circleR ||
                circleX < rectLeft - circleR ||
                circleY > rectTop + circleR ||
                circleY < rectBottom - circleR
            ) {
                return false;
            }

            // 计算圆心到矩形的水平和垂直距离
            var deltaX = Math.max(rectLeft - circleX, 0, circleX - rectRight);
            var deltaY = Math.max(circleY - rectTop, 0, rectBottom - circleY);
            // 判断最短距离是否小于等于圆的半径
            return deltaX * deltaX + deltaY * deltaY <= circleR * circleR
        }

        const indexs: number[] = []

        if (fun(rectHeight + rectY, mindY, mindX, rectWidth + rectX)) {
            indexs.push(0)
        }
        if (fun(rectHeight + rectY, mindY, rectX, mindX)) {
            indexs.push(1)
        }
        if (fun(mindY, rectY, rectX, mindX)) {
            indexs.push(2)
        }
        if (fun(mindY, rectY, mindX, rectWidth + rectX)) {
            indexs.push(3)
        }
        return indexs
    }

    private getIndexByPoint(p: Point): any {
        const mindX = this.bounds.w / 2 + this.bounds.x
        const mindY = this.bounds.h / 2 + this.bounds.y

        const inTop = p.y > mindY
        const inBottom = p.y < mindY
        const inLeft = p.x < mindX
        const inRight = p.x > mindX

        const indexs: number[] = []

        if (inRight && inTop) {
            indexs.push(0)
        }
        if (inLeft && inTop) {
            indexs.push(1)
        }
        if (inLeft && inBottom) {
            indexs.push(2)
        }
        if (inRight && inBottom) {
            indexs.push(3)
        }
        return indexs
    }

    private getIndexByLine(line: Line): any {
        const { x1, y1, x2, y2 } = line
        let segment = {
            start: { x: x1, y: y1 },
            end: { x: x2, y: y2 }
        }
        const w = this.bounds.w / 2
        const h = this.bounds.h / 2
        const indexs: number[] = []

        if (this.checkBoundsIntersect(segment, this.bounds.x + w, this.bounds.y + h, w, h)) {
            indexs.push(0)
        }

        if (this.checkBoundsIntersect(segment, this.bounds.x, this.bounds.y + h, w, h)) {
            indexs.push(1)
        }

        if (this.checkBoundsIntersect(segment, this.bounds.x, this.bounds.y, w, h)) {
            indexs.push(2)
        }

        if (this.checkBoundsIntersect(segment, this.bounds.x + w, this.bounds.y, w, h)) {
            indexs.push(3)
        }

        return indexs
    }

    /** 四叉树插入元素 */
    insert(leaf: Bounds) {
        const { x, y, w, h } = leaf
        let rect: Rect = { x, y, w, h }
        if (this.nodes.length) {
            const indexs = this.getIndex(rect)
            for (let i = 0; i < indexs.length; i++) {
                this.nodes[indexs[i]].insert(leaf)
            }
            return
        }

        this.leafs.push(leaf)

        if (this.leafs.length > this.maxNum && this.deep < this.maxDeep) {
            this.split()
            for (let i = 0; i < this.leafs.length; i++) {
                const { x, y, w, h } = this.leafs[i]
                let rect: Rect = { x, y, w, h }
                const indexs = this.getIndex(rect)
                for (let j = 0; j < indexs.length; j++) {
                    this.nodes[indexs[j]].insert(this.leafs[i])
                }
            }
            this.leafs = []
        }
    }

    clear() {
        if (this.nodes.length) {
            for (let i = 0; i < this.nodes.length; i++) {
                this.nodes[i].clear()
            }
        }

        this.leafs = []
        this.nodes = []
    }

    /** 线段是否与矩形相交 */
    checkBoundsIntersect(segment: Segment, x: number, y: number, w: number, h: number) {
        let s1 = {
            start: { x, y },
            end: { x: x + w, y }
        }
        if (segmentsIntersect(segment, s1)) return true
        let s2 = {
            start: { x, y },
            end: { x, y: y + h }
        }
        if (segmentsIntersect(segment, s2)) return true
        let s3 = {
            start: { x: x + w, y: y + h },
            end: { x: x + w, y }
        }
        if (segmentsIntersect(segment, s3)) return true
        let s4 = {
            start: { x: x + w, y: y + h },
            end: { x, y: y + h }
        }
        if (segmentsIntersect(segment, s4)) return true

        return false
    }

}